//Given a m x n grid filled with non-negative numbers, find a path from top left
// to bottom right, which minimizes the sum of all numbers along its path. 
//
// Note: You can only move either down or right at any point in time. 
//
// 
// Example 1: 
//
// 
//Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
//Output: 7
//Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
// 
//
// Example 2: 
//
// 
//Input: grid = [[1,2,3],[4,5,6]]
//Output: 12
// 
//
// 
// Constraints: 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 200 
// 0 <= grid[i][j] <= 100 
// 
// Related Topics 数组 动态规划 
// 👍 879 👎 0


package leetcode.editor.cn;

//Java：Minimum Path Sum
class P64MinimumPathSum {
    public static void main(String[] args) {
        Solution solution = new P64MinimumPathSum().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[][] memo;

        public int minPathSum(int[][] matrix) {
            memo = new int[matrix.length][matrix[0].length];
            memo[0][0] = matrix[0][0];
            for (int i = 1; i < memo.length; i++) {
                memo[i][0] = memo[i - 1][0] + matrix[i][0];
            }
            for (int j = 1; j < memo[0].length; j++) {
                memo[0][j] = memo[0][j - 1] + matrix[0][j];
            }
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[0].length; j++) {
                    memo[i][j] = matrix[i][j] + Math.min(memo[i - 1][j], memo[i][j - 1]);

                }
            }
            return memo[matrix.length - 1][matrix[0].length - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}